The subject matter disclosed herein generally relates to motion planning systems, and more particularly to space partitioning for motion planning.
Motion planning for a robot or vehicle typically uses a sample-based planning algorithm to construct a graph or tree that represents feasible paths to various locations in an area under consideration. Algorithms that can be used to construct the graph typically rely on random-number generators and placing random samples around a vehicle configuration space as constrained by obstacles and having a free edge to another node in the graph. The vehicle configuration space defines an area under consideration for identifying one or more feasible paths to safely guide the vehicle around any obstacles. The random samples are either connected to the graph or rejected based on feasibility of connection with the graph. In a completely random sampling strategy, a high number of samples can be rejected especially if the vehicle configuration space is highly constrained, such as in a dense, obstacle-rich environment. The vehicle configuration space is typically difficult to determine a priori in a closed-form with a high degree of granularity and accuracy.